/**
 * Find the maximum total from the top of the triangle to the bottom by
 * moving to adjacent numbers on the row below.
 */

#include <iostream>
#include "euler/prime_test.hpp"
#include "euler.h"

BEGIN_PROBLEM(69, solve_problem_69)
	PROBLEM_TITLE("Find the value of n <= 10^6 that maximizes n/phi(n)")
	PROBLEM_ANSWER("510510")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("ln(n)*ln(ln(n))")
	PROBLEM_SPACE_COMPLEXITY("1")
END_PROBLEM()

static void solve_problem_69()
{
	const int N = 1000000;

	int product = 1;
	for (int p = 2; product*p <= N; p = euler::next_prime(p))
		product *= p;

	std::cout << product << std::endl;
}
